#ifndef OPTFRAME_PATTERNIMPROVEMENTFULL_HPP_
#define OPTFRAME_PATTERNIMPROVEMENTFULL_HPP_

#include "../../OptFrame/Heuristic.hpp"
#include "../../OptFrame/Evaluator.hpp"

#include <algorithm>

/*
 struct bestPos
 {
 int periodo;
 int rota;
 int posicao;
 };*/

class PatternImprovementFull: public Heuristic<RepPRVP, MemPRVP>
{
private:
	PRVPEvaluator& eval;
	PRVPProblemInstance& pPRVP;
	double static const inf = 99999999;

	vector<int> decompoeEscolha(int escolha)
	{
		vector<int> periodos;
		int p = pPRVP.nPeriod - 1;
		while (escolha != 0)
		{
			if (escolha % 2 == 1)
			{
				periodos.push_back(p);
			}
			escolha = escolha / 2;
			p--; //passando para o proximo periodo
		}

		return periodos;
	}

	double removeCliInRoute(int id, vector<vector<int> >& rt, vector<double> & cap)
	{
		double custo = 0;//custo da remoção do cliente
		for (unsigned int r = 0; r < rt.size(); r++)
			for (unsigned int c = 0; c < rt.at(r).size(); c++)
			{
				if (id == rt.at(r).at(c))
				{
					if (rt.at(r).size() == 1)//se tiver somente um elemento
					{
						custo = -(*pPRVP.dist)(0, rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), 0);
						rt.at(r).erase(rt.at(r).begin() + c);
						//atualizando a capacidade dessa rota
						cap.at(r) -= pPRVP.dados->at(id).at(DEMANDA);
						return custo;
					}
					else
					{
						//retornando o custo da remoção desse cliente
						if (c == 0)
						{
							custo = (*pPRVP.dist)(0, rt.at(r).at(c + 1)) - (*pPRVP.dist)(0, rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), rt.at(r).at(c + 1));
						}
						else if (c == rt.at(r).size() - 1)
						{
							custo = (*pPRVP.dist)(rt.at(r).at(c - 1), 0) - (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), 0);
						}
						else
						{
							custo = (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c + 1)) - (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), rt.at(r).at(c + 1));
						}
					}
					rt.at(r).erase(rt.at(r).begin() + c);
					//atualizando a capacidade dessa rota
					cap.at(r) -= pPRVP.dados->at(id).at(DEMANDA);
					return custo;
				}
			}

		return custo;

	}

	double removeCli(RepPRVP& rep, int c, ADS& ads, vector<vector<double> >& cap)
	{
		double custo = 0;
		for (int i = 0; i < ads.getLocal_cli().at(c).size(); i++)
		{
			custo += removeCliInRoute(c, rep.at(ads.getLocal_cli().at(c).at(i)), cap.at(ads.getLocal_cli().at(c).at(i)));
		}

		return custo;

	}

	double bestInsertion(vector<vector<int> > routes, int periodo, int cli, bestPos & pos, vector<double>& cap, double taxa)
	{

		//melhor valor de inserção
		double best_insert = inf;
		//melhor posicao de inserção
		pos.periodo = periodo;

		double aux_insert = 0;

		//pegando a matriz de distancia
		Matrix<double>& dist = (*pPRVP.dist);

		/*cout<<dist<<endl;
		 exit(1);*/

		//verificando a melhor posição em todos os periodos
		for (int r = 0; r < routes.size(); r++)
		{
			if (routes.at(r).size() == 0)// se a rota estiver vazia
			{
				aux_insert = dist(0, cli) + dist(cli, 0);

				if (aux_insert < best_insert)
				{
					best_insert = aux_insert;
					pos.rota = r;
					pos.posicao = 0;
				}

			}
			else //caso a rota não estiver vazia
			{
				//verificando se ao adicionar o cliente a essa rota não estoura a capacidade do veículo
				if (cap.at(r) + pPRVP.dados->at(cli).at(DEMANDA) <= (pPRVP.capacidade * taxa))
				{
					//testando se a melhor posição fica entre o depósito e o primeiro cliente da rota "r"
					aux_insert = dist(0, cli) + dist(cli, routes.at(r).at(0)) - dist(0, routes.at(r).at(0));

					if (aux_insert < best_insert)
					{
						best_insert = aux_insert;
						pos.rota = r;
						pos.posicao = 0;
					}

					//testando para as demais posições
					for (int c = 0; c < routes.at(r).size() - 1; c++)
					{
						aux_insert = dist(routes.at(r).at(c), cli) + dist(cli, routes.at(r).at(c + 1)) - dist(routes.at(r).at(c), routes.at(r).at(c + 1));
						if (aux_insert < best_insert)
						{
							best_insert = aux_insert;
							pos.rota = r;
							pos.posicao = c + 1;
						}
					}
					//testando se a melhor posição fica entre o ultimo cliente da rota "r" e o depósito
					aux_insert = dist(routes.at(r).at(routes.at(r).size() - 1), cli) + dist(cli, 0) - dist(routes.at(r).at(routes.at(r).size() - 1), 0);
					if (aux_insert < best_insert)
					{
						best_insert = aux_insert;
						pos.rota = r;
						pos.posicao = routes.at(r).size();
					}
				}
			}
		}

		return best_insert;
	}

public:

	using Heuristic<RepPRVP, MemPRVP>::exec; // prevents name hiding

	PatternImprovementFull(PRVPEvaluator& _eval, PRVPProblemInstance& _pPRVP) :
		eval(_eval), pPRVP(_pPRVP)
	{
	}

	virtual ~PatternImprovementFull()
	{
	}

	virtual void exec(Solution<RepPRVP>& s, double timelimit, double target_f)
	{
		Evaluation<MemPRVP>& e = eval.evaluate(s.getR());

		exec(s, e, timelimit, target_f);

		delete &e;
	}

	virtual void exec(Solution<RepPRVP>& s, Evaluation<MemPRVP>& e, double timelimit, double target_f)
	{
		bool alterado = false;

		double delta_fo = 0;
		double inf_antes, inf_dps, delta_inf = 0;
		EvaluationPRVP& eTemp = eval.evaluate(s.getR());
		double aux = eTemp.evaluation();
		delete &eTemp;

		do
		{

			vector<int> clients;
			//randomizando a ordem dos clientes
			for (int c = 1; c <= pPRVP.nCli; c++)
			{
				clients.push_back(c);
			}
			random_shuffle(clients.begin(), clients.end());

			//calculando quando da capacidade do veículo está sendo utilizada
			vector < vector<double> > cap_utilizada;

			for (int p = 0; p < s.getR().size(); p++)
			{
				vector<double> aux;
				for (int r = 0; r < s.getR().at(p).size(); r++)
				{
					double cap = 0;
					for (int c = 0; c < s.getR().at(p).at(r).size(); c++)
					{
						cap += pPRVP.dados->at(s.getR().at(p).at(r).at(c)).at(DEMANDA);
					}
					aux.push_back(cap);
				}
				cap_utilizada.push_back(aux);
			}

			alterado = false;
			for (int i = 0; i < clients.size(); i++)
			{
#ifdef DEBUG
				if (!pPRVP.chech_solution(s))
				{
					cout << "inicio -- cli: " << clients.at(i) << endl;
					s.print();
					getchar();
				}
#endif

				//cout << "capacidade antes: " << cap_utilizada << endl;

				//calculando a inviabilidade antes
				inf_antes = 0;
				for (int p = 0; p < cap_utilizada.size(); p++)
				{
					for (int r = 0; r < cap_utilizada.at(p).size(); r++)
					{
						inf_antes += min(0.0, pPRVP.capacidade - cap_utilizada.at(p).at(r));
					}
				}

				//cout << "invi antes: " << inf_antes << endl;

				RepPRVP& rep = s.getR();

				//fazendo uma cópia da capacidade utilizada até então
				vector < vector<double> > &cap_util_atual = cap_utilizada;

				double custoRemocao = removeCli(rep, clients.at(i), e.getM(), cap_util_atual); // removendo o cliente indice "i" da solução

				//estruturas auxiliares para cada combinação de periodos de cada cliente
				double eval_escolha = 0;
				vector<bestPos> pos_aux;

				double bestEval = inf;
				vector<bestPos> bestPosCli;

				//tentando realizar insercoes que não ultrapassem a carga do caminhão
				double taxa = 1.0;
				do
				{
					//para cada uma das combinações
					for (int escolha = 0; escolha < pPRVP.dados->at(clients.at(i)).at(NCOMB); escolha++)
					{
						//cout << "escolha : " << escolha << endl;
						eval_escolha = custoRemocao;
						pos_aux.clear();

						//decompondo a primeir escolha
						vector<int> periodos = decompoeEscolha(pPRVP.dados->at(clients.at(i)).at(NCOMB + escolha + 1));
						//para cada periodo decomposto

						//	fazer as inserções por periodo guardando os menores valores
						for (int p = 0; p < periodos.size(); ++p)
						{
							bestPos aux;
							eval_escolha += bestInsertion(rep.at(periodos.at(p)), periodos.at(p), clients.at(i), aux, cap_util_atual.at(periodos.at(p)), taxa);
							pos_aux.push_back(aux);
						}

						if (eval_escolha < -0.001)
							alterado = true;

						if (eval_escolha < bestEval)
						{
							bestEval = eval_escolha;
							bestPosCli = pos_aux;
						}
					}

					taxa += 0.1;
				} while (bestEval > inf - 10000);

				//marcando os periodos que foram removidos
				for (int j = 0; j < e.getM().getLocal_cli().at(clients.at(i)).size(); ++j)
				{
					e.getM().getStatus().at(e.getM().getLocal_cli().at(clients.at(i)).at(j)) = true;
				}

				//atualizando a ADS para o cliente selecionado
				e.getM().getLocal_cli().at(clients.at(i)).clear();

				//teste de inviabilidade
				inf_dps = 0;
				//inserindo o cliente na melhor posição em cada período
				for (int bpos = 0; bpos < bestPosCli.size(); bpos++)
				{
					int periodo = bestPosCli.at(bpos).periodo; //periodo
					int rota = bestPosCli.at(bpos).rota; // rota
					int posicao = bestPosCli.at(bpos).posicao; // posição de inserção

					e.getM().getStatus().at(periodo) = true;

					//fazendo a inserção
					s.getR().at(periodo).at(rota).insert(s.getR().at(periodo).at(rota).begin() + posicao, clients.at(i));

					//atualizando a memória com as novas posições do cliente
					e.getM().getLocal_cli().at(clients.at(i)).push_back(periodo);

					//atualizando as capacidades das rotas
					cap_utilizada.at(periodo).at(rota) += pPRVP.dados->at(clients.at(i)).at(DEMANDA);

				}

				// ----------------- calculo 0(1)
				//se houve melhora, atualizando o delta
				if (bestEval < -0.001 || bestEval > 0.001)
					delta_fo += bestEval;

				//calculando a inviabilidade dps

				//calculando a inviabilidade antes
				inf_dps = 0;
				for (int p = 0; p < cap_utilizada.size(); p++)
				{
					for (int r = 0; r < cap_utilizada.at(p).size(); r++)
					{
						inf_dps += max(0.0, cap_utilizada.at(p).at(r) - pPRVP.capacidade);
					}
				}

				//calculando a inviabilidade
				delta_inf += inf_antes + inf_dps;

				// --------------------- fim calculo

#ifdef DEBUG
				if (!pPRVP.chech_solution(s))
				{
					cout << "Fim -- cli: " << clients.at(i) << endl;
					s.print();
					getchar();
				}
#endif
			}


		} while (alterado);

		e.getM().setDelta(delta_fo);
		e.getM().setDelta_inf(delta_inf);

		eval.evaluate(e, s.getR()); // updates 'e'
	}

};

#endif /*OPTFRAME_PATTERNIMPROVEMENTFULL_HPP_*/
